in English
Биография
Обзор
магистерской
работы
Библиотека
Ссылки
Результаты
поиска
Записки двух
программистов
Куркчи Вячеслав Андреевич
kourktchi@ukrtop.com
магистрант группы ПО-99, ФВТИ
научный руководитель:
Ладыженский Юрий Валентинович
тема магистерской работы:
Параллельные алгоритмы для решения задач на графах.
Введение
Графы являются очень распространенной структурой данних, и задачи, связанные с ними, находят свое применение в различных областях науки и техники: эти задачи решаются при проектировании БИС, при распараллеливании вычислительных и других процессов, при организации ассоциативной памяти, в теории конечных автоматов, потоков в сетях и др. Задачи на графах многие из нас часто решают в повседневной жизни, даже не зная об этом.
К сожалению, большая часть задач на графах - NP-полные, что в значительной степени усложняет поиск решения. Однако задачи этого класу часто просто необходимо решить. Это обусловило появление направления, изучающего приближенные, или эвристические, алгоритмы. Большая часть NP-полных задач сводится к ЗЦЛП, что позволяет использовать в качестве решения любые локальные максимумы (минимумы). Такое решение, конечно же, не является оптимальным, но допустимо.
Процесс решения задачи большой размерности, даже приближенным алгоритмом может быть весьма длительным, что справедливо для всех задач и любых алгоритмов. Для ускорения поиска решений, используют параллельные алгоритмы. Временная сложность параллельных алгоритмов обычно, как минимум на порядок ниже, чем у аналогичных последовательных, а иногда и относится к другому классу.
Для рассмотрения была выбрана задача о наибольшем независимом множестве вершин. Эта задача была выбрана по двум причинам. Во-первых, она является фундаментальной, и к ней сводятся задачи о наименьшем покрытии, о совершенном паросочетании, о доминирующем множестве и многие другие. То есть большинство алгоритмов для решения этой задачи можно распространить на многие другие. А во-вторых, у этой задачи довольно большое число приложений, что делает поиск эффективного алгоритма для решения этой задачи необходимым. В силу последнего, задача о наибольшем независимом множестве вершин стала в последнее время очень популярной среди исследователей.
Подмножество вершин графа является независимым, если никакие две вершины из этого множества несмежны.
Пример независимых множеств на графе.
